package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author By ZengPeng
 * @Description
 * @date in  2021/2/5 14:08
 * @Modified By
 */
public class 力扣_501_二叉搜索树中的众数 {

    public static void main(String[] args) {

        System.out.println(new 力扣_501_二叉搜索树中的众数().findMode(TreeNode.initRoot()));
    }
    /**
     题目：给你一个含重复值的二叉搜索树（BST）的根节点 root ，
     找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
     如果树中有不止一个众数，可以按 任意顺序 返回。

     假定 BST 满足如下定义：
     结点左子树中所含节点的值 小于等于 当前节点的值
     结点右子树中所含节点的值 大于等于 当前节点的值
     左子树和右子树都是二叉搜索树

     示例 1：
     输入：root = [1,null,2,2]
     输出：[2]

     示例 2：
     输入：root = [0]
     输出：[0]

     分析：【Good ♥♥♥】
     1.先简单的完成：用list保存，再变量统计  -- 执行用时：8 ms, 在所有 Java 提交中击败了8.81%的用户
     2.先序遍历：因为是二叉搜索树保证了有序. 用
        变量 n  ： 当前统计数
            numb： 当前重复值个数,
            max ： 最多次重复次数
            list:  最多次重复元素的集合

     边界值 & 注意点：
     1.
     **/

    public int[] findMode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        recursive(root,list );
        Map<Integer,Integer> map = new HashMap<>();
        for (Integer aList : list)
            map.put(aList, map.getOrDefault(aList, 0) + 1);
        int max=0;
        for (Integer value : map.values())
            max= Math.max(max,value);
        List<Integer> res = new ArrayList<>();
        for (Integer key : map.keySet()) {
            if(map.get(key)==max)
                res.add(key);
        }
        //输出结果
        int[] rs = new int[res.size()];
        for (int i = 0; i < rs.length; i++)
           rs[i]= res.get(i);
        return rs;
    }

    private void recursive(TreeNode root, List<Integer> res) {
        if(root.left!=null)
            recursive(root.left, res);
        res.add(root.val);
        if(root.right!=null)
           recursive(root.right, res);
    }

    //返回我下面有多少个值与我相同
    private int recursive2(TreeNode root,  List<Integer> res) {
        int me = 1;
        int left =0;
        int right =0;
        if(root.left!=null){
            left = recursive2(root.left, res);
            if(root.val == root.left.val){
                me+=left;
            }
        }
        if(root.right!=null){
             right = recursive2(root.right, res);
            if(root.val == root.right.val){
                me+=right;
            }
        }
        me = Math.max(me,Math.max(left,right));
        return me;
    }
}
